# -*- coding: utf-8 -*-
# @Time : 2023/12/18 16:04
# @Author  : lining
# @FileName: 二叉搜索树插入.py
"""
https://leetcode.cn/problems/insert-into-a-binary-search-tree/
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。


"""
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


node5 = TreeNode(7)
node6 = TreeNode(9)
node2 = TreeNode(8, node5, node6)
node7 = TreeNode(11)
node8 = TreeNode(13)
node3 = TreeNode(12, node7, node8)
# 根
node4 = TreeNode(10, node2, node3)
node9 = TreeNode(0)

class TreeInsert():
    def __init__(self, root, value):
        self.value = value
        self.root = root

    def tree_insert(self, node, parent, is_left):
        if node is None:
            node = TreeNode(self.value)
            if is_left:
                parent.left = node
            else:
                parent.right = node
            return
        if self.value < node.val:
            self.tree_insert(node.left, node, True)
        else:
            self.tree_insert(node.right, node, False)
        return self.root

    def insert_tree(self, node):
        if node is None:
            return TreeNode(self.value)
        elif node.val < self.value:
            node.right = self.insert_tree(node.right)
        elif node.val > self.value:
            node.left = self.insert_tree(node.left)
        return node


a = TreeInsert(node4, 1).insert_tree(node4)
print(a)
